<!-------- @HEADER
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 !  Zoltan Toolkit for Load-balancing, Partitioning, Ordering and Coloring
 !                  Copyright 2012 Sandia Corporation
 !
 ! Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
 ! the U.S. Government retains certain rights in this software.
 !
 ! Redistribution and use in source and binary forms, with or without
 ! modification, are permitted provided that the following conditions are
 ! met:
 !
 ! 1. Redistributions of source code must retain the above copyright
 ! notice, this list of conditions and the following disclaimer.
 !
 ! 2. Redistributions in binary form must reproduce the above copyright
 ! notice, this list of conditions and the following disclaimer in the
 ! documentation and/or other materials provided with the distribution.
 !
 ! 3. Neither the name of the Corporation nor the names of the
 ! contributors may be used to endorse or promote products derived from
 ! this software without specific prior written permission.
 !
 ! THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
 ! EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 ! IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 ! PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
 ! CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 ! EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 ! PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 ! PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 ! LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 ! NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 ! SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 !
 ! Questions? Contact Karen Devine	kddevin@sandia.gov
 !                    Erik Boman	egboman@sandia.gov
 !
 ! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 !
 ! @HEADER
-------> 
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<head>
   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   <meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; Linux 2.4.2-2smp i686) [Netscape]">
  <meta name="sandia.approval_type" content="formal">
  <meta name="sandia.approved" content="SAND2007-4748W">
  <meta name="author" content="Zoltan PI">

   <title>Zoltan User's Guide:  Hypergraph Algorithms</title>
</head>
<body bgcolor="#FFFFFF">

<div align=right><b><i><a href="ug.html">Zoltan User's Guide</a>&nbsp;
|&nbsp; <a href="ug_alg_phg.html">Next</a>&nbsp; |&nbsp; <a href="ug_alg_reftree.html">Previous</a></i></b></div>

<h2>
<a NAME="Hypergraph"></a>Hypergraph partitioning</h2>


Hypergraph partitioning is a useful partitioning and
load balancing method when connectivity data is available. It can be
viewed as a more sophisticated alternative to
the traditional graph partitioning.
<p>A hypergraph consists of vertices and hyperedges. A hyperedge
connects
one or more vertices.
A graph can be cast as a hypergraph in one of two ways: either every
pair of neighboring vertices form a hyperedge, or a vertex and all
its neighbors form a hyperedge.
The hypergraph model is well
suited to parallel computing, where vertices correspond to data objects
and hyperedges represent the communication requirements. The basic
partitioning problem is to partition the vertices into <i>k</i>
approximately equal sets such that the number of cut hyperedges is
minimized. Most partitioners (including Zoltan-PHG) allows a more
general
model where both vertices and hyperedges can be assigned weights.
It has been
shown that the hypergraph model gives a more accurate representation
of communication cost (volume) than the graph model. In particular,
for sparse matrix-vector multiplication, the hypergraph model
<strong>exactly</strong> represents communication volume. Sparse
matrices can be partitioned either along rows or columns;
in the row-net model the columns are vertices and each row corresponds
to an hyperedge, while in the column-net model the roles of vertices
and hyperedges are reversed. </p>
<p>Zoltan contains a native parallel hypergraph partitioner, called PHG
(Parallel HyperGraph partitioner). In addition, Zoltan provides
access to <a href="https://bmi.osu.edu/%7Eumit/software.htm">PaToH</a>,
a serial hypergraph partitioner.
Note that PaToH is not part of Zoltan and should be obtained
separately from the <a href="https://bmi.osu.edu/%7Eumit/software.htm">
PaToH web site</a>.
Zoltan-PHG is a fully parallel multilevel hypergraph partitioner. For
further technical description, see <a
 href="ug_refs.html#hypergraph-ipdps06">[Devine et al, 2006]</a>.<br>
</p>
<p>
A new feature available in Zoltan 3.0 is the ability to assign selected
objects (vertices) to a particular part ("fixed vertices").  
When objects are fixed,
Zoltan will not migrate them out of the user assigned part.
See the descriptions of the
<i><a href="ug_query_lb.html#ZOLTAN_NUM_FIXED_OBJ_FN">ZOLTAN_NUM_FIXED_OBJ_FN</a></i>
and
<i><a href="ug_query_lb.html#ZOLTAN_FIXED_OBJ_LIST_FN">ZOLTAN_FIXED_OBJ_LIST_FN</a></i>
query functions for a discussion of how you can define these two
functions to fix objects to parts. Both PHG and PaToH support this
feature.

<p>
For applications that already use Zoltan to do graph partitioning, 
it is easy to upgrade to hypergraph partitioning. For many applications,
the hypergraph model is superior to the graph model, but in some cases
the graph model should be preferred. PHG can also be used as a pure
graph partitioner. See the section
<a href="ug_graph_vs_hg.html">graph vs. hypergraph</a> partitioning
for further details. </p>


<br>&nbsp;
<table WIDTH="100%" NOSAVE >
<tr>
<td VALIGN=TOP><b>Method String:</b></td>

<td><b>HYPERGRAPH</b></td>
</tr>

<tr>
<td><b>Parameters:</b></td>

<td></td>
</tr>

<tr>
<td VALIGN=TOP><i>&nbsp;&nbsp;&nbsp; HYPERGRAPH_PACKAGE</i></td>

<td>The software package to use in partitioning the hypergraph.&nbsp;
<br><i><a href=ug_alg_phg.html>PHG (Zoltan, the default)</a></i>&nbsp;
<br><i><a href=ug_alg_patoh.html>PATOH</a></i>&nbsp;
</tr>

</table>

<p>
<hr WIDTH="100%">[<a href="ug.html">Table of Contents</a>&nbsp; | <a href="ug_alg_phg.html">Next:&nbsp;
PHG</a>&nbsp; |&nbsp; <a href="ug_alg_reftree.html">Previous:&nbsp;
Refinement Tree Partitioning</a>&nbsp; |&nbsp; <a href="https://www.sandia.gov/general/privacy-security/index.html">Privacy and Security</a>]
</body>
</html>
